import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
 * */
public class leetcode_3 {

//    /**
//     * 思想：Set集合的特性
//     *
//     * */
    public int lengthOfLongestSubstring(String s) {

        int n = s.length();
        int ans = 0;

        for (int i = 0; i < n; i++)
            for (int j = i + 1; j <= n; j++)
                if (allUnique(s,i,j))
                    ans = Math.max(ans,j-i);

        return ans;
    }

    public boolean allUnique(String s ,int start , int end){

        Set<Character> set = new HashSet<>();
        for (int i = start; i < end; i++) {
            Character ch = s.charAt(i);
            if (set.contains(ch))
                return false;
            set.add(ch);
        }
        return true;
    }

//    /**
//     * 滑动窗口法
//     * */
//    public int lengthOfLongestSubstring(String s) {
//        int n = s.length();
//        Set<Character> set = new HashSet<>();
//        int ans = 0, i = 0, j = 0;
//
//        while(i < n && i < n){
//            if (!set.contains(s.charAt(j))){
//                set.add(s.charAt(j++)); //charAt：返回指定索引的字符
//                ans = Math.max(ans , j - i); //哪个大选哪个
//            }else {
//                set.remove(s.charAt(i++));
//            }
//        }
//        return ans;
//    }

    /**
     * 优化的滑动窗口
     * 如果 s[j]在 [i, j) 范围内有与 j 重复的字符，我们不需要逐渐增加 i 。
     * 我们可以直接跳过 [i，j ′ ] 范围内的所有元素，并将 i 变为 j’ + 1
     * */
//     public int lengthOfLongestSubstring(String s) {
//        int ans = 0 , n = s.length();
//        Map<Character,Integer> map = new HashMap<>();
//
//        for (int i = 0 , j = 0 ; j < n ; j ++){
//            if (map.containsKey(s.charAt(j))){
//                //i 变为 j’ + 1
//                i = Math.max(map.get(s.charAt(j)) , i);
//            }
//            //i 变为 j’ + 1
//            ans = Math.max(ans , j - i + 1);
//            //增加 i
//            map.put(s.charAt(j), j + 1);
//        }
//        return ans;
//    }

    /**
     * 利用max函数
     * */
//    public int lengthOfLongestSubstring(String s) {
//        int n = s.length(), ans = 0;
//        int[] index = new int[128]; // current index of character
//        // try to extend the range [i, j]
//        for (int j = 0, i = 0; j < n; j++) {
//            i = Math.max(index[s.charAt(j)], i);
//            ans = Math.max(ans, j - i + 1);
//            index[s.charAt(j)] = j + 1;
//        }
//        return ans;
//    }

    public static void main(String[] args) {
        leetcode_3 l3 = new leetcode_3();

        int a = l3.lengthOfLongestSubstring("ashbdkjhahsvbdkhbasd");
        System.out.println(a);
    }
}
